package main

type MyHashMap struct {
	//数组+链表
	hashmap []*Node
	//容量
	capacity int
}

type Node struct {
	Key   int
	Value int
	Next  *Node
}

/** Initialize your data structure here. */
func Constructor() MyHashMap {
	return MyHashMap{
		capacity: 64,
		hashmap:  make([]*Node, 64),
	}
}

/** value will always be non-negative. */
func (this *MyHashMap) Put(key int, value int) {
	index := key % 64
	node := this.hashmap[index]
	if node == nil {
		n := &Node{Key: key, Value: value}
		this.hashmap[index] = n
	} else {
		//是否存在的标记
		has := false
		for node.Next != nil {
			if node.Key == key {
				node.Value = value
				has = true
				break
			} else {
				node = node.Next
			}
		}
		if node.Key == key {
			node.Value = value
			has = true
		}
		if !has {
			n := &Node{Key: key, Value: value}
			node.Next = n
		}
	}
}

/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
func (this *MyHashMap) Get(key int) int {
	index := key % 64
	node := this.hashmap[index]
	value := -1
	if node == nil {
		return value
	} else {
		for node != nil {
			if node.Key == key {
				value = node.Value
				break
			} else {
				node = node.Next
			}
		}
	}
	return value
}

/** Removes the mapping of the specified value key if this map contains a mapping for the key */
func (this *MyHashMap) Remove(key int) {
	index := key % 64
	node := this.hashmap[index]
	temp := node
	prev := node
	for temp != nil {
		if temp.Key == key {
			if temp == node {
				this.hashmap[index] = temp.Next
				return
			}
			prev.Next = temp.Next
			return
		} else {
			prev = temp
			temp = temp.Next
		}
	}
}

func main() {
	hashMap := Constructor()
	value := hashMap.Get(11)
	println(value)
	hashMap.Put(22, 83)
	hashMap.Put(39, 4)
	hashMap.Put(34, 88)
	hashMap.Put(72, 99)
	hashMap.Remove(33)
	hashMap.Put(58, 77)
	hashMap.Put(23, 61)
	hashMap.Remove(34)
	hashMap.Remove(66)
	hashMap.Remove(90)
	hashMap.Put(72, 83)
	hashMap.Put(50, 98)
	hashMap.Put(93, 97)
	hashMap.Put(74, 95)
	hashMap.Remove(81)
	hashMap.Put(56, 1)
	hashMap.Put(86, 80)
	hashMap.Put(93, 91)
	hashMap.Put(13, 1)
	hashMap.Remove(93)
	hashMap.Put(63, 11)
	hashMap.Put(62, 63)
	//get
	hashMap.Put(71, 98)
	hashMap.Put(97, 96)
	hashMap.Put(65, 47)
	hashMap.Remove(93)
	hashMap.Put(30, 78)
	hashMap.Put(31, 40)
	hashMap.Put(67, 86)
	hashMap.Put(84, 11)
	hashMap.Put(3, 19)
	hashMap.Put(30, 97)
	hashMap.Put(3, 36)
	hashMap.Put(92, 43)
	hashMap.Remove(71)
	hashMap.Remove(86)
	value = hashMap.Get(86)
	println(value)
	hashMap.Put(71, 91)
	hashMap.Put(18, 29)
	hashMap.Put(75, 44)
	hashMap.Put(35, 81)
	hashMap.Remove(58)
	hashMap.Put(12, 69)
	hashMap.Remove(58)
	hashMap.Put(84, 9)

	value = hashMap.Get(22)
	println(value)
}
